/**
 * problem_024.cpp
 * Copyright (C) 2011 - xrose
 */
#include <iostream>
#include <string>
#include <stdio.h>
//--
using namespace std;

class PERMU
{
    private:
        string s;
    public:
        PERMU();
        PERMU(string);
        string nextPermu();
        string nextPermu(string);
        string prevPermu();
        string prevPermu(string);
        string nthPermu(int);
        string nthPermu(string, int);
};
PERMU::PERMU()
{
    s="0";
}
PERMU::PERMU(string s_in)
{
    s=s_in;
}
string PERMU::nextPermu()
{
    string str = s;
    int l_sin = str.length();
    int i, j;
    char c_tmp, c_tem;
    for(i=l_sin-1; i>0; i--)
    {
        if(str[i]>str[i-1])
        {
            ++str[i-1];
            --str[l_sin -1];
            for(j=i; j<(l_sin + i + 1)/2.0; j++)
            {
                c_tem = str[l_sin + i -1 - j];
                str[l_sin + i -1 - j] = str[j];
                str[j] = c_tem;
            }
            break;
        }

    }
    cout<<"str: "<<str<<endl;
    return str;
}
string PERMU::nextPermu(string s_in)
{
    string str;
    str = s_in;
    int l_sin = str.length();
    int i, j;
    char c_tem;
    for(i=l_sin-1; i>0; i--)
    {
        if(str[i]>str[i-1])
        {
            ++str[i-1];
            --str[l_sin -1];
            for(j=i; j<(l_sin + i + 1)/2.0; j++)
            {
                c_tem = str[l_sin + i -1 - j];
                str[l_sin + i -1 - j] = str[j];
                str[j] = c_tem;
            }
            break;
        }

    }
    cout<<"str: "<<str<<endl;
    return str;
}

string PERMU::nthPermu(int n)
{
    int cnt = 0;
    string str = s;
    int l_sin = str.length();
    int i, j;
    char c_tem;
    while(cnt<n)
    {
        for(i=l_sin-1; i>0; i--)
        {
//            cout<<"i="<<i<<endl;
            if((str[i]>str[i-1]))
            {
                //++str[i-1]; //=gia tri nho nhat ma` van lon hon str[i-1] trong cac phan phia sau
                c_tem = str[i];
//                cout<<"++c_tem-->"<<c_tem<<endl;
                for(j=i; j<l_sin; j++)
                {
                    if((c_tem>str[j]) && (str[j]>str[i-1]))
                    {
                        c_tem = str[j];
                    }
                }
//                cout<<"i-->"<<i<<"c_tem: "<<c_tem<<endl;
                for(j=i; j<l_sin; j++)
                {
                    if(str[j] == c_tem)
                    {
                        str[j] = str[i-1];
                        str[i-1] = c_tem;
                    }
                }
                for(j=i; j<l_sin; j++)
                {
                    for(int k=l_sin-1; k>j; k--)
                    {
                        if(str[k]<str[k-1])
                        {
                            c_tem = str[k];
                            str[k] = str[k-1];
                            str[k-1] = c_tem;
                        }
                    }
                }

            break;
            }
        }
        cnt++;
//        cout<<"cout-->"<<cnt<<":"<<str<<endl;
    }
    return str;
}

int main (int argc, char const* argv[])
{

    PERMU per("0123456789");
    cout<<per.nthPermu(1000000-1);
    return 0;
}
